Pattern search is a simple yet powerful machine vision tool. Given a template pattern and an image, the pattern search objective is to find all instances of the pattern in the image. It involves two steps, a search step and a matching step. The search step places the pattern at all valid locations, scales, rotations of the image being searched. The matching step determines the goodness of the match between the pattern and the subset of the image centered at a given image location. A normalized correlation method (Ballard D H and Brown C M, “Computer Vision”, Prentice-Hall Inc. 1982, pp. 68–70) has been widely used as the matching method in many machine vision applications because the match score of normalized correlation is largely independent of linear variations in object shading caused by reflectivity or illumination variation. However, pattern search based on the normalized correlation method is inherently computationally demanding since it requires operations between two (pattern and image) regions on all valid image locations. Even with the state-of-the-art computers, it is still difficult to achieve real-time performance when the image is large or frequent (for tracking) or includes color or 3D (or higher dimensionality). Furthermore, normalized correlation does not work well when the pattern being searched is subject to rotation or size variation. The match score could drop significantly even with only a few degrees of rotation or a few percent of size change occurring.
One prior art approach to rotation and scale invariance is to rotate and scale the pattern template and try all possible scale and rotation combinations. However, this imposes an even greater computational demand that cannot be accomplished using prior art methods. Another prior art approach is the use of a geometric pattern matching method such as PatMax introduced by Cognex (Silver, B, “Geometric Pattern Matching for General-Purpose Inspection in Industrial Machine Vision”, Intelligent Vision '99 Conference—Jun. 28–29, 1999). This approach uses geometric information in place of pixel grid-based correlation. For example, it interprets a square as four line segments and a football as two arcs. It extracts key geometric features within an object image such as boundary encoding and measures characteristics such as shape, dimensions, angle, arcs, and shading. It then corresponds the spatial relationships between the key features of the pattern template and the new image. However, this prior art approach requires high edge contrast and low noise between patterns and background to reliably extract the key geometric features. It fails when edges of a pattern are not well defined. This is the inherent problem when using a geometric approach in place of a pixel grid based approach.
A recent change to the prior art approach has been disclosed in the U.S. patent application Ser. No. 10/255,016 filed Sep. 24, 2002 by Lee et. al entitled, “Fast Regular Shaped Pattern Searching” which is incorporated in its entirety herein. The patent application describes use of an accumulation transformation of an input image to facilitate fast search for regular shaped patterns. The invention is distinguished from this prior art by the fast search for general shaped patterns, which is done with different methods.